# 作者：一只牛吗
# 2025 年03月 05日 04时 24分 16秒
# 1278599690@qq.com
import random
import time


class Sort:
    def __init__(self, num=10):
        '''
        :param num:需要排序的list长度
        '''
        self.len = num
        self.sort_list = [0] * num
        # self.sort_list = [3, 87, 2, 93, 78, 56, 61, 38, 12, 40]
        # self.sort_list = [26, 99, 48, 54, 9, 95, 47, 55, 99, 76]
        self.random_data()

    def random_data(self):
        for i in range(self.len):
            self.sort_list[i] = random.randint(0, 99)

    def partition(self, low, high):
        pivot = self.sort_list[high]  # 选择最后一个元素作为基准值
        k = low  # k 是小于基准值的元素的位置
        for i in range(low, high):
            if self.sort_list[i] < pivot:
                self.sort_list[i], self.sort_list[k] = self.sort_list[k], self.sort_list[i]
                k += 1
        # 将基准值放到正确的位置
        self.sort_list[k], self.sort_list[high] = self.sort_list[high], self.sort_list[k]
        return k  # 返回基准值的位置

    def quick_sort(self, low, high):
        if low < high:
            pivot = self.partition(low, high)  # 计算基准值的位置
            self.quick_sort(low, pivot - 1)  # 递归排序左半部分
            self.quick_sort(pivot + 1, high)  # 递归排序右半部分
        else:
            return

    def adjust_heap(self, pos, list_len):
        arr = self.sort_list
        dad = pos
        son = 2 * dad + 1
        while son < list_len:
            if (son + 1) < list_len and arr[son] < arr[son + 1]:
                son = son + 1
            if arr[dad] < arr[son]:
                arr[dad], arr[son] = arr[son], arr[dad]
                dad = son
                son = dad * 2 + 1
            else:
                break

    def heap_sort(self):
        for parent in range(self.len // 2 - 1, -1, -1):
            self.adjust_heap(parent, self.len)
        arr = self.sort_list
        arr[0], arr[self.len - 1] = arr[self.len - 1], arr[0]
        for list_len in range(self.len - 1, 1, -1):
            self.adjust_heap(0, list_len)
            arr[0], arr[list_len - 1] = arr[list_len - 1], arr[0]

    def test_time_use(self, sort_func, *args, **kwargs): # 一种回调函数的形式
        start = time.time()
        sort_func(*args, **kwargs)
        end = time.time()
        print(f'总计耗时：{end - start}秒')


if __name__ == "__main__":
    # list1 = Sort()
    # print(list1.sort_list)
    # list1.quick_sort(0, list1.len - 1)
    # print(list1.sort_list)
    my_sort = Sort(10000)
    # print(my_sort.sort_list)
    # my_sort.heap_sort()
    # print(my_sort.sort_list)
    my_sort.test_time_use(my_sort.quick_sort,0, 10000 - 1)
